package LInkedList;

import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:岁亮亮
 * Date:2024-05-21
 * TIME:21:04
 */
public class MyLinkedList implements MyList {

    private static class ListNode {
        int value;
        ListNode next;
        ListNode pre;

        ListNode(int value, ListNode next, ListNode pre) {
            this.value = value;
            this.next = next;
            this.pre = pre;
        }
    }
    private ListNode head;
    private ListNode tail;
    private int size;

    @Override
    public boolean add(int data) {
        addLast(data);
        return true;
    }

    /***
     * 1.添加头节点的时候 头节点确认是这个新添加的节点
     * 2.若原本链表为空 更新尾节点 否则更新原来头节点的前驱
     * @param data 添加节点的数据域
     */
    @Override
    public void addFirst(int data) {
        ListNode cur = this.head;
        ListNode newNode = new ListNode(data,cur,null);
        this.head = newNode;
        if(cur == null){
            this.tail = newNode;
        }
        else {
            cur.pre = newNode;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode last = this.tail;
        ListNode newNode = new ListNode(data,null,last);
        this.tail = newNode;
        if(last == null){
            this.head = newNode;
        }
        else {
            last.next = newNode;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        checkPositionIndex(index);
        if(index == this.size()){
            addLast(data);
        }
        else {
            addBefore(data,node(index));
        }

    }

    private void addBefore(int data, ListNode node) {
        ListNode cur = node.pre;
        ListNode newNode = new ListNode(data,node,cur);
        node.pre = newNode;
        if(cur == null){
            this.head = newNode;
        }
        else {
            cur.next = newNode;
        }
    }

    private ListNode node(int index){
        if(index < (this.size() >> 1)){
            ListNode cur = this.head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur;
        }
        else {
            ListNode last = this.tail;
            for (int i = this.size() -1 ; i >index ; i--) {
                last = last.pre;
            }
            return last;
        }
    }

    private void checkPositionIndex(int index) {
        if(index < 0 || index > this.size()){
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public boolean contains(int key) {
        return indexOf(key) >= 0;
    }

    @Override
    public int indexOf(int key) {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int count = 0;
        while (cur != null){
            if(cur.value == key){
                return count;
            }
            count++;
            cur = cur.next;
        }
        return -1;
    }
    private int unLink(ListNode node){
        int value = node.value;
        ListNode pre = node.pre;
        ListNode next = node.next;
        if(pre == null){
            this.head = next;
        }
        else {
            pre.next = next;
            node.pre = null;
        }
        if(next == null){
            this.tail = pre;
        }
        else {
            next.pre = pre;
            node.next = null;
        }
        node.value = -1;
        return value;
    }

    @Override
    public void remove(int key) {
        ListNode cur = this.head;
        if( cur == null){
            throw new NoSuchElementException();
        }
        if(indexOf(key) == -1){
            return;
        }
        unLink(node(indexOf(key)));



    }

    @Override
    public int removeIndex(int index) {
        checkElementIndex(index);
        return unLink(node(index));

    }

    private void checkElementIndex(int index) {
        if(index < 0 || index >= this.size()){
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public int removeFirst() {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        return unLinkedFirst(cur);
    }

    private int unLinkedFirst(ListNode cur) {
        //assert cur == head && cur != null
        int element = cur.value;
        ListNode next = cur.next;
        this.head = next;
        if(next == null){
            this.tail = null;
        }
        else {
            next.pre = null;
        }
        cur.next = null;// help GC
        cur.value = -1;
        return element;

    }

    @Override
    public int removeLast() {
        ListNode cur = this.tail;
        if(cur == null){
            throw new NoSuchElementException();
        }
        return unLinkedLast(cur);
    }

    private int unLinkedLast(ListNode cur) {
        //assert cur == last && cur != null
        int element = cur.value;
        ListNode pre = cur.pre;
        cur.value = -1;
        cur.pre = null;//help GC
        this.tail = pre;
        if(pre == null){
            this.head = null;
        }
        else {
            pre.next = null;
        }
        return element;
    }

    @Override
    public void removeAllKey(int key) {


    }
    public void reverseLinkedList(){
        ListNode cur = this.head;
        ListNode first = this.head;
        ListNode second = this.head.next;
        while (second != null){
            ListNode mid = second.next;
            second.pre = mid;
            second.next = first;
            first = second;
            second = mid;
        }
        cur.next = null;
        cur.pre = second;
        this.head = first;
    }
    @Override
    public int size() {
       ListNode cur = this.head;
       int count = 0;
       while (cur != null){
           cur = cur.next;
           count++;
       }
       return count;
    }

    @Override
    public void clear() {
        ListNode cur = this.head;
        while (cur != null){
            ListNode mid = cur;
            mid.value = -1;
            mid.pre = null;
            mid.next = null;
            cur = cur.next;
        }

    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
